package 题目集.动态规划.最长递增子序列;

import org.junit.Test;

/**
 * 这是错误版本
 * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
 */
public class ch07_最长上升子序列个数 {
    int[] ends;
    int[] lens;

    /**
     *  思路：记录每个长度出现的次数，当遍历到某个数时，其长度出现的次数为，前一个长度出现的次数+当前长度已经出现的次数
     *  这种思路会有问题，没有考虑最长递增子序列ends数组中小数会覆盖大数的问题。
     * @param nums
     * @return
     */
    public int findNumberOfLIS(int[] nums) {
        lens = new int[nums.length];
        ends = new int[nums.length];
        ends[0] = nums[0];
        lens[0]++;
        int len = 1;  //当前最长长度
        for (int i = 1; i < nums.length; i++) {
            int index = find(nums[i], 0, len - 1);
            if (index != 0) {
                lens[index] += lens[index - 1];
            } else {
                lens[index]++;
            }
            ends[index] = nums[i];
            if (index == len) {
                len++;
            }
        }
        return lens[len - 1];
    }

    public int find(int v, int l, int r) {
        while (l <= r) {
            int m = l + r >> 1;
            if (v < ends[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if (r >= 0 && ends[r] >= v) return r;
        return l;
    }

    @Test
    public void test() {
        int[] arr = {6, 2, 3};
        int numberOfLIS = findNumberOfLIS(arr);
        System.out.println(numberOfLIS);
    }
}
